package main.java.algorithms;

import main.java.utils.SortTestHelper;

/**
 * @author Wrb
 * @date 2019/5/22 15:32
 */
public class InsertionSort implements Sort {
	@Override
	public void sort(int[] arr, int n) {
		for (int i = 1; i < n; i++) {
			int e = arr[i];
			int j;
			for ( j = i; j > 0 && arr[j - 1] > e; j--) {
				SortTestHelper.swap(arr, j, j - 1);
			}
			arr[j] = e;
		}
	}

	//对arr[l...r]范围的数组进行插入排序
	public static void sort(int arr[], int l, int r) {
		for (int i = l; i <= r; i++) {
			int e = arr[i];
			int j;
			for ( j = i; j > 0 && arr[j - 1] > e; j--) {
				SortTestHelper.swap(arr, j, j - 1);
			}
			arr[j] = e;
		}
	}

}
